package com.fang.string.rotation;


/**
 * 如果对于一个字符串A，将A的前面任意一部分挪到后边去形成的字符串称为A的旋转词。比如A="12345",
 * A的旋转词有"12345","23451","34512","45123"和"51234"。对于两个字符串A和B，请判断A和B是否互为旋转词。
 * 给定两个字符串A和B及他们的长度lena，lenb，请返回一个bool值，代表他们是否互为旋转词。 <br>
 * 测试样例： <br>
 * "cdab",4,"abcd",4 <br>
 * 返回：true
 */
public class RotationWord {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		String str = "abgctabc";
		RotationWord rotationWord = new RotationWord();
//		int[] next = rotationWord.calNext(str.toCharArray(), str.length());
//		for (int i : next) {
//			System.out.print(i + "   ");
//		}

		//String aa = "abgctabgctabc";
		String bb = "abgctabc";
		int[] next = rotationWord.calNext(bb.toCharArray(), bb.length());
		for (int i : next) {
			System.out.print(i + "   ");
		}
		System.out.println("");
		next = rotationWord.getNext(bb);
		for (int i : next) {
			System.out.print(i + "   ");
		}
		System.out.println("");
		
//		boolean flag1 = rotationWord.kmp(aa.toCharArray(), bb.toCharArray(), next);
//		System.out.println(flag1);
		
//		boolean flag = rotationWord.chkRotation(aa, aa.length(), bb, bb.length());
//		System.out.println(flag);

	}

	public boolean chkRotation(String A, int lena, String B, int lenb) {
		if (lena != lenb || A == null || B == null)
			return false;

		String temp = A + A;
		int[] next = calNext(B.toCharArray(), B.length());
		for (int i : next) {
			System.out.print(i + "   ");
		}
		return kmp(temp.toCharArray(), B.toCharArray(), next);
	}

	public boolean kmp(char[] A, char[] B, int[] next) {
		int aCount = 0;
		int bCount = 0;

		while (bCount < B.length && aCount < A.length) {
			if (A[aCount] == B[bCount]) {
				aCount++;
				bCount++;
				if (bCount == B.length)
					return true;
			} else {
				int tempNext = next[bCount];
				if (tempNext == -1) {
					if(bCount == 0){
						aCount++;
					}
					bCount = 0;
					
				} else {
					bCount = tempNext;
				}
			}
		}
		return false;
	}

	public int[] calNext(char[] str, int len) {
		int i = 0, j = 0;
		int[] next = new int[len];
		next[0] = -1;
		while(i< len-1) {
			j = next[i];
			while ((j >= 0) && (str[j] != str[i]) ) {
				j = next[j];
			}
			if ((j >= 0) && (str[i] == str[j])) {
				next[++i] = j + 1;
			} else {
				next[++i] = 0;
			}
		}
		return next;
	
	}
	
	public  int[] getNext(String ps)
	{
	    char[] strKey = ps.toCharArray();
	    int[] next = new int[strKey.length];

	    // 初始条件
	    int j = 0;
	    int k = -1;
	    next[0] = -1;
	 
	    // 根据已知的前j位推测第j+1位
	    while (j < strKey.length - 1)
	    {
	        if (k == -1 || strKey[j] == strKey[k])
	        {
	            next[++j] = ++k;
	        }
	        else
	        {
	            k = next[k];
	        }
	    }
	     return next;
	}
}
